package DoblePointer;//给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
//
// 如果相等，返回 true ；否则，返回 false 。 
//
// 注意：如果对空文本输入退格字符，文本继续为空。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "ab#c", t = "ad#c"
//输出：true
//解释：S 和 T 都会变成 “ac”。
// 
//
// 示例 2： 
//
// 
//输入：s = "ab##", t = "c#d#"
//输出：true
//解释：s 和 t 都会变成 “”。
// 
//
// 示例 3： 
//
// 
//输入：s = "a##c", t = "#a#c"
//输出：true
//解释：s 和 t 都会变成 “c”。
// 
//
// 示例 4： 
//
// 
//输入：s = "a#c", t = "b"
//输出：false
//解释：s 会变成 “c”，但 t 仍然是 “b”。 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length, t.length <= 200 
// s 和 t 只含有小写字母以及字符 '#' 
// 
//
// 
//
// 进阶： 
//
// 
// 你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？ 
// 
//
// 
// Related Topics 栈 双指针 字符串 模拟 👍 323 👎 0


import java.util.Stack;

//leetcode submit region begin(Prohibit modification and deletion)
class backspaceCompare {
    public boolean backspaceCompare1(String s, String t) {
        /**
         * 用两个栈，但需要额外空间
         * 遇到 # 则弹出栈顶
         * */
        Stack<Character> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();
        for (char ch:s.toCharArray()
             ) {
            if(ch!='#'){
                stack1.push(ch);
            }else if(!stack1.isEmpty()){
                stack1.pop();
            }
        }
        for (char ch:t.toCharArray()
        ) {
            if(ch!='#'){
                stack2.push(ch);
            }else if(!stack2.isEmpty()){
                stack2.pop();
            }
        }
        //两个栈大小不一样 直接返回false
        if (stack1.size()!=stack2.size()){
            return false;
        }
        while (!stack1.isEmpty() && !stack2.isEmpty()){
            if (stack1.pop()!=stack2.pop()){
                return false;
            }
        }
        return true;
    }

    public boolean backspaceCompare(String s, String t) {

        /**
         * 双指针逆序遍历字符串
         * 考虑字符是否有效只和它后面的退格符有关，与前面无关
         * 因此 从后遍历，遇到退格符跳过，直到遇到非退格符，比较
         * */
        int i = s.length() - 1, j = t.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                //遍历字符串当遇到退格符，需要跳过的计数加1
                if (s.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    //否则遇到正常字符，若需要跳过的计数大于0，跳过当前字符
                    skipS--;
                    i--;
                } else {
                    //若不用跳过，则记录到该指针位置
                    break;
                }
            }
            //同理
            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            //两个指针一次查找结束，如果两个遍历没有到末尾，判断字符是否相等
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            } else {
                //若有一个已经遍历结束，另一个未结束，直接不符合
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;

    }
}
//leetcode submit region end(Prohibit modification and deletion)
